package com.itheima.algorithm.dynamicprogramming;

import java.util.Arrays;

/**
 * <h3>0-1 背包问题（item不可以重复） - 动态规划</h3>
 */
public class KnapsackProblem {
    /*
        1. n个物品都是固体，有重量和价值
        2. 现在你要取走不超过 10克 的物品
        3. 每次可以不拿或全拿，问最高价值是多少

            编号 重量(g)  价值(元)                       简称
            1   4       1600           黄金一块   400    A
            2   8       2400           红宝石一粒 300    R
            3   5       30             白银一块          S
            4   1       1_000_000      钻石一粒          D
        1_001_630 贪心结

        1_002_400 正确解
     */

    /*
        行对应物品 列对应容量
            0   1   2   3   4   5   6   7   8   9   10
        0   0   0   0   0   A   A   A   A   A   A   A
        1   0   0   0   0   A   A   A   A   R   R   R
        2   0   0   0   0   A   A   A   A   R   R   R
        3   0   D   D   D   D   DA  DA  DA  DA  DR  DR

        if(装不下) {
            dp[i][j] = dp[i-1][j]
        } else { 装得下
            dp[1][8] = max(dp[0][8], R)
            dp[3][5] = max(dp[2][5], D + dp[2][4])
            dp[i][j] = max(dp[i-1][j], item.value + dp[i-1][j-item.weight])
        }
     */
    static class Item {
        int index;
        int weight;
        int value;

        public Item(int index, int weight, int value) {
            this.index = index;
            this.weight = weight;
            this.value = value;
        }

        public int unitValue() {
            return value / weight;
        }

        @Override
        public String toString() {
            return "Item(" + index + ")";
        }
    }

    public static void main(String[] args) {
        Item[] items = new Item[]{
                new Item(1, 4, 1600),
                new Item(2, 8, 2400),
                new Item(3, 5, 30),
                new Item(4, 1, 10_000)
        };
        System.out.println(select2(items, 10));
    }

    /*
        二维数组
     */
    static int select(Item[] items, int total) {
        int[][] dp = new int[items.length][total + 1];
        Item item0 = items[0];
        for (int j = 0; j < total + 1; j++) { // 装得下
            if (j >= item0.weight) {
                dp[0][j] = item0.value;
            } else {                         // 装不下
                dp[0][j] = 0;
            }
        }
        for (int i = 1; i < dp.length; i++) {
            Item item = items[i];
            for (int j = 0; j < total + 1; j++) {
                if (j >= item.weight) { // 装得下
                    dp[i][j] = Integer.max(dp[i - 1][j], item.value + dp[i - 1][j - item.weight]);
                } else {                // 装不下
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[dp.length - 1][total];
    }

    /*
        一维数组
     */
    static int select2(Item[] items, int total) {
        int[] dp = new int[total + 1];
        Item item0 = items[0];
        for (int j = 0; j < total + 1; j++) { // 装得下
            if (j >= item0.weight) {
                dp[j] = item0.value;
            } else {                         // 装不下
                dp[j] = 0;
            }
        }
        System.out.println(Arrays.toString(dp));
        for (int i = 1; i < items.length; i++) {
            Item item = items[i];
            for (int j = total; j >= 0; j--) {
                if (j >= item.weight) { // 装得下
                    dp[j] = Integer.max(dp[j], item.value + dp[j - item.weight]);
                }
            }
        }
        return dp[total];
    }
}
